/*
package com.example.demo.jdk.map;

import com.example.demo.jdk.collection.MyCollection;

import javax.swing.tree.TreeNode;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.*;

*/
/**
 * @author: htc
 * @date: Created in 10:40 2018/11/26.
 *//*

public class MyHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {

    */
/**
     * 默认初始化容量
     *//*

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    */
/**
     * 最大容量
     *//*

    static final int MAXIMUM_CAPACITY = 1 << 30;

    */
/**
     * 默认加载因子
     *//*

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    */
/**
     * 链表散列成红黑树时的阈值
     * 一个桶中的存储方式由链表转换成树的阈值。即当桶中bin的数量超过TREEIFY_THRESHOLD时使用树来代替链表。默认值是8
     *//*

    static final int TREEIFY_THRESHOLD = 8;

    */
/**
     * 红黑树散列成链表的阈值
     * 当执行resize操作时，当桶中bin的数量少于UNTREEIFY_THRESHOLD时使用链表来代替树
     *//*

    static final int UNTREEIFY_THRESHOLD = 6;

    */
/**
     * 当桶中的bin被树化时最小的hash表容量。
     * （如果没有达到这个阈值，即hash表容量小于MIN_TREEIFY_CAPACITY，当桶中bin的数量太多时会执行resize扩容操作）这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。
     *//*

    static final int MIN_TREEIFY_CAPACITY = 64;

    static class Node<K, V> implements Map.Entry<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;

        public Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public final K getKey() {
            return key;
        }

        @Override
        public final V getValue() {
            return value;
        }

        @Override
        public String toString() {
            return key + "=" + value;
        }

        @Override
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        @Override
        public V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        @Override
        public final boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj instanceof Map.Entry) {
                Map.Entry<?, ?> e = (Map.Entry<?, ?>) obj;
                if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) {
                    return true;
                }
            }
            return false;
        }
    }

    */
/**
     * @param key
     * @return
     *//*

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    */
/**
     * 如果对象x的类是C，如果C实现了Comparable<C>接口，那么返回C，否则返回nul
     *
     * @param x
     * @return
     *//*

    static Class<?> comparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class<?> c;
            Type[] ts, as;
            Type t;
            */
/**
             * ParameterizedType 这个类可以用来检验泛型是否被参数化
             *//*

            ParameterizedType p;
            if ((c = x.getClass()) != String.class) {
                //如果x是个字符串对象，则直接返回String.class（因为String实现了Comparable<C>接口）
                return c;
            }
            //如果 c 不是字符串类，获取c直接实现的接口（如果是泛型接口则附带泛型信息）
            if ((ts = c.getGenericInterfaces()) != null) {
                //遍历接口数组
                for (int i = 0; i < ts.length; i++) {
                    // 如果当前接口t是个泛型接口
                    if (((t = ts[i]) instanceof ParameterizedType)
                            // 如果该泛型接口t的原始类型p 是 Comparable 接口
                            && ((p = (ParameterizedType) t).getRawType() == Comparable.class)
                            // 如果该Comparable接口p只定义了一个泛型参数
                            && (as = p.getActualTypeArguments()) != null
                            && as.length == 1
                            // 如果这一个泛型参数的类型就是c，那么返回c
                            && as[0] == c) {
                        return c;
                    }
                }
            }
        }
        return null;
    }

    */
/**
     * 如果x所属的类是kc，返回k.compareTo(x)的比较结果
     * 如果x为空，或者其所属的类不是kc，返回0
     *
     * @param kc
     * @param k
     * @param x
     * @return
     *//*

    static int compareComparables(Class<?> kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 : ((Comparable) k).compareTo(x));
    }

    */
/**
     * 返回一个大于且最接近cap的值，并且该值是2的指数次方
     *
     * @param cap
     * @return
     *//*

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    */
/* ---------------- Fields -------------- *//*


    transient Node<K, V>[] table;

    transient Set<Map.Entry<K, V>> entrySet;

    transient int size;

    transient int modCount;

    */
/**
     * 容量* 加载因子
     *//*

    int threshold;

    final float loadFactor;

    */
/* ---------------- Public operations -------------- *//*


    public MyHashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        }

        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        }
        */
/**
         * ,Float.isNaN()该方法用于描述非法的float,经过多次运算float值可能会出现非法情况
         *//*

        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        }

        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

    public MyHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public MyHashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

    public MyHashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

    */
/**
     * Implements Map.putAll and Map constructor
     *
     * @param m
     * @param evict
     *//*

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) {
                float ft = ((float) s / loadFactor) + 1.0F;
                int t = ((ft < (float) MAXIMUM_CAPACITY) ? (int) ft : MAXIMUM_CAPACITY);
                if (t > threshold) {
                    threshold = tableSizeFor(t);
                }
            } else if (s > threshold) {
                resize();
            }
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public V get(Object key) {
        Node<K, V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    */
/**
     * desc:
     * 当链表节点数量达到一定阈值（8）会将链表上的节点再组织成一棵红黑树。红黑树是一种二叉树，每个父节点可以由左右两个节点
     * 当put一个新元素时，如果该元素键的hash值小于当前节点的hash值的时候，就会作为当前节点的左节点；hash值大于当前节点hash值得时候作为当前节点的右节点。
     * hash值相同的时候会先尝试看是否能够通过Comparable进行比较一下两个对象（当前节点的键对象和新元素的键对象），
     * 要想看看是否能基于Comparable进行比较的话，首先要看该元素键是否实现了Comparable接口，
     * 此时就需要用到comparableClassFor方法来获取该元素键的Class，然后再通过compareComparables方法来比较两个对象的大小。
     * 如果两者不具有compare的资格，或者compare之后仍然没有比较出大小。那么就要通过一个决胜局再比一次，这个决胜局就是tieBreakOrder方法。
     *
     * @param hash
     * @param key
     * @return
     *//*

    final Node<K, V> getNode(int hash, Object key) {
        Node<K, V>[] tab;
        Node<K, V> first, e;
        int n;
        K k;
        if ((tab = table) != null
                && (n = tab.length) > 0
                && (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash
                    && ((k = first.key) == key || (key != null && key.equals(k)))) {
                return first;
            }
            if ((e = first.next) != null) {
                if (first instanceof TreeNode) {
                    return ((TreeNode<K, V>) first).;
                }
            }
        }
    }

    static final class TreeNode<K, V> extends MyLinkedHashMap.Entry<K, V> {
        TreeNode<K, V> parent;
        TreeNode<K, V> left;
        TreeNode<K, V> right;
        TreeNode<K, V> prev;
        boolean red;

        TreeNode(int hash, K key, V value, MyHashMap.Node<K, V> next) {
            super(hash, key, value, next);
        }

        */
/**
         * return root of tree containing this node
         *
         * @return
         *//*

        final TreeNode<K, V> root() {
            for (TreeNode<K, V> r = this, p; ; ) {
                */
/**
                 * root节点的父节点为null
                 *//*

                if ((p = r.parent) == null) {
                    return r;
                }
                r = p;
            }
        }

        */
/**
         * 确保给定的根是其桶的第一个节点。
         *
         * @param tab
         * @param root
         * @param <K>
         * @param <V>
         *//*

        static <K, V> void moveRootToFront(Node<K, V>[] tab, TreeNode<K, V> root) {
            int n;
            if (root != null
                    && tab != null
                    && (n = tab.length) > 0) {
                int index = (n - 1) & root.hash;
                TreeNode<K, V> first = (TreeNode<K, V>) tab[index];
                if (root != first) {
                    Node<K, V> rn;
                    tab[index] = root;
                    TreeNode<K, V> rp = root.prev;
                    if ((rn = root.next) != null) {
                        ((TreeNode<K, V>) rn).prev = rp;
                    }
                    if (rp != null) {
                        rp.next = rn;
                    }
                    if (first != null) {
                        first.prev = root;
                    }
                    root.next = first;
                    root.prev = null;
                }
                assert checkInvariants(root);
            }
        }

        */
/**
         * 从root节点p开始，根据给定的hash值和key值找到相应的节点
         *
         * @param h
         * @param k
         * @param kc
         * @return
         *//*

        final TreeNode<K, V> find(int h, Object k, Class<?> kc) {
            TreeNode<K, V> p = this;
            do {
                int ph, dir;
                K pk;
                TreeNode<K, V> pl = p.left, pr = p.right, q;
                if ((ph = p.hash) > h) {
                    p = pl;
                } else if (ph < h) {
                    p = pr;
                } else if ((pk = p.key) == k || (k != null && k.equals(pk))) {
                    return p;
                } else if (pl == null) {
                    p = pr;
                } else if (pr == null) {
                    p = pl;
                } else if ((kc != null
                        || (kc = comparableClassFor(k)) != null)
                        && (dir = compareComparables(kc, k, kc)) != 0) {
                    p = (dir < 0) ? pl : pr;
                } else if ((q = pr.find(h, k, kc)) != null) {
                    return q;
                } else {
                    p = pl;
                }

            } while (p != null);
            return null;
        }

        */
/**
         * 从root节点开始调用find方法
         *
         * @param h
         * @param k
         * @return
         *//*

        final TreeNode<K, V> getTreeNode(int h, Object k) {
            return ((parent != null) ? root() : this).find(h, k, null);
        }

        */
/**
         * 用这个方法来比较两个对象，返回值要么大于0，要么小于0，不会为0
         * 也就是说这一步一定能确定要插入的节点要么是树的左节点，要么是右节点，不然就无法继续满足二叉树结构了
         * <p>
         * 先比较两个对象的类名，类名是字符串对象，就按字符串的比较规则
         * 如果两个对象是同一个类型，那么调用本地方法为两个对象生成hashCode值，再进行比较，hashCode相等的话返回-1
         *
         * @param a
         * @param b
         * @return
         *//*

        static int tieBreakOrder(Object a, Object b) {
            int d;
            if (a == null
                    || b == null
                    || (d = a.getClass().getName().compareTo(b.getClass().getName())) == 0) {
                d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1);
            }
            return d;
        }

        */
/**
         * Forms tree of the nodes linked from this node
         *
         * @param tab
         *//*

        final void treeify(Node<K, V>[] tab) {
            TreeNode<K, V> root = null;
            for (TreeNode<K, V> x = this, next; x != null; x = next) {
                next = (TreeNode<K, V>) x.next;
                x.left = x.right = null;
                if (root == null) {
                    x.parent = null;
                    x.red = false;
                    root = x;
                } else {
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    for (TreeNode<K, V> p = root; ; ) {
                        int dir, ph;
                        K pk = p.key;
                        if ((ph = p.hash) > h) {
                            dir = -1;
                        } else if (ph < h) {
                            dir = 1;
                        } else if ((kc == null && (kc = comparableClassFor(k)) == null)
                                || (dir = compareComparables(kc, k, pk)) == 0) {
                            dir = tieBreakOrder(k, pk);
                        }
                        TreeNode<K, V> xp = p;
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            x.parent = xp;
                            if (dir <= 0) {
                                xp.left = x;
                            } else {
                                xp.right = x;
                            }
                            root = balanceInsertion(root, x);
                            break;
                        }
                    }
                }
            }
            moveRootToFront(tab, root);
        }

        */
/**
         * 去树形话
         *
         * @param map
         * @return
         *//*

        final Node<K, V> untreeify(MyHashMap<K, V> map) {
            Node<K, V> hd = null, tl = null;
            for (Node<K, V> q = this; q != null; q = q.next) {
                Node<K, V> p = map.replacementNode(q, null);
                if (tl == null) {
                    hd = p;
                } else {
                    tl.next = p;
                }
            }
            return hd;
        }

        */
/**
         * @param map
         * @param tab
         * @param h
         * @param k
         * @param v
         * @return
         *//*

        final TreeNode<K, V> putTreeVal(MyHashMap<K, V> map, Node<K, V>[] tab, int h, K k, V v) {
            Class<?> kc = null;
            boolean searched = false;
            TreeNode<K, V> root = (parent != null) ? root() : this;
            for (TreeNode<K, V> p = root; ; ) {
                int dir, ph;
                K pk;
                if ((ph = p.hash) > h) {
                    dir = -1;
                } else if (ph < h) {
                    dir = 1;
                } else if ((pk = p.key) == k || (k != null && k.equals(pk))) {
                    return p;
                } else if ((kc == null && (kc = comparableClassFor(k)) == null)
                        || (dir = compareComparables(kc, k, pk)) == 0) {
                    if (!searched) {
                        TreeNode<K, V> q, ch;
                        searched = true;
                        if (((ch = p.right) != null && (q = ch.find(h, k, kc)) != null) ||
                                ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null)) {
                            return q;
                        }
                    }
                    dir = tieBreakOrder(k, pk);
                }

                TreeNode<K, V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    Node<K, V> xpn = xp.next;
                    TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn);
                    if (dir <= 0) {
                        xp.left = x;
                    } else {
                        xp.right = x;
                    }
                    x.next = x;
                    x.parent = x.prev = xp;
                    if (xpn != null) {
                        ((TreeNode<K, V>) xpn).prev = x;
                    }
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }
    }

    */
/**
     * @return
     *//*

    final Node<K, V>[] resize() {
        return null;
    }


     */
/* -----------------------LinkedHashMap support------------------------------------- *//*


    Node<K, V> replacementNode(Node<K, V> p, Node<K, V> next) {
        return new Node<K, V>(p.hash, p.key, p.value, next);
    }
}
*/
